package q765_minSwapsCouples;

import CommonClass.UF;

public class Solution_2 {
    /*
    并查集：
    这里需要先了解一个数学条件 例如如果有两对情侣其坐错了位置
    那么我们以两个位置为一个块 假设是这样的情况 0-2 1-3 此时我们就认为出现了一个环 因为 0应该和1连在一起 2应该和3连在一起
    同样的 如果三对情侣坐错了位置 同样也是出现了一个环穿过了三个块 此时就需要交换两次
    这里浅显的先得出一个结论 也就是 交换的次数 = 情侣对数 - 环的数量 这个环也就是一个并查集能够实现的 簇
    那么如何将不同的块连接到一个簇之中 此时先考虑一对情侣的特点 也就是其数字 / 2是相同的
    所以假设row[i] / 2, row[i + 1] / 2其中有坐错的情侣 假设是后面这个row[i + 1] / 2 union时就会将其引到对应的块中去
    最后仍然能够形成一个闭环
     */
    public int minSwapsCouples(int[] row) {
        int n = row.length / 2;
        UF uf = new UF(n);
        for (int i = 0; i < row.length; i += 2) {
            uf.union(row[i] / 2, row[i + 1] / 2);
        }
        return n - uf.count();
    }
}
